import java.util.*;

public class Leetcode433 {
    public static void main(String[] args) {
        System.out.println(minMutation("AACCGGTT", "AAACGGTA", new String[]{"AACCGGTA", "AACCGCTA", "AAACGGTA"}));
    }

    private static final char[] ALL_GENE = {'A', 'C', 'G', 'T'};

    public static int minMutation(String start, String end, String[] bank) {
        Set<String> visited = new HashSet<>();
        Collections.addAll(visited, bank);

        if(!visited.contains(end)) {
            return -1;
        }

        Queue<String> queue = new LinkedList<>();
        queue.add(start);

        Map<String, Integer> count = new HashMap<>();
        count.put(start, 0);

        while (!queue.isEmpty()) {
            String cur = queue.poll();
            char[] current = cur.toCharArray();

            for (int i = 0; i < current.length; i++) {
                for (char gene : ALL_GENE) {
                    if (current[i] == gene) {
                        continue;
                    }

                    char[] next = current.clone();
                    next[i] = gene;
                    String nextStr = new String(next);

                    if (!visited.contains(nextStr)) {
                        continue;
                    }

                    if (nextStr.equals(end)) {
                        return count.get(cur) + 1;
                    }

                    if (count.containsKey(nextStr)) {
                        if (count.get(nextStr) <= count.get(cur)) {
                            continue;
                        }
                    }

                    queue.add(nextStr);
                    count.put(nextStr, count.get(cur) + 1);
                }
            }
        }

        return -1;
    }
}
